/*-
 * Copyright 2012 Guram Dukashvili
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */
//---------------------------------------------------------------------------
#include "sys.h"
#include "str.h"
#include "idx.h"
//---------------------------------------------------------------------------
static __inline__ void lookup_zero_bit(const void * bitmap,uintptr_t size,uintptr_t * pos)
{
  uintptr_t p = *pos;

  while( p < size && (p & 7) != 0 ){
    if( (((uint8_t *) bitmap)[p >> 3] & (1u << (p & 7))) == 0 ) goto e1;
    p++;
  }

  while( p + 8 <= size && (p & (SIZEOF_INTMAX_T * 8 - 1)) != 0 ){
    if( ((uint8_t *) bitmap)[p >> 3] != 0xFF ) break;
    p += 8;
  }

  while( p + SIZEOF_INTMAX_T * 8 <= size ){
    if( *(uintmax_t *) ((uintptr_t) bitmap + (p >> 3)) != (uintmax_t) ~(uintmax_t) 0 ) break;
    p += SIZEOF_INTMAX_T * 8;
  }

#if SIZEOF_INTMAX_T > 4
  if( p + 4 * 8 <= size && *(uint32_t *) ((uintptr_t) bitmap + (p >> 3)) == (uint32_t) ~(uint32_t) 0 ) p += 4 * 8;
#endif

  if( p + 2 * 8 <= size && *(uint16_t *) ((uintptr_t) bitmap + (p >> 3)) == (uint16_t) ~(uint16_t) 0 ) p += 2 * 8;

  if( p + 8 <= size && ((uint8_t *) bitmap)[p >> 3] == (uint8_t) ~(uint8_t) 0 ) p += 8;

  while( p < size && (((uint8_t *) bitmap)[p >> 3] & (1u << (p & 7))) != 0 ) p++;

e1:
  *pos = p;
}
//-----------------------------------------------------------------------------
static __inline__ void lookup_non_zero_bit(const void * bitmap,uintptr_t size,uintptr_t * pos)
{
  uintptr_t p = *pos;

  while( p < size && (p & 7) != 0 ){
    if( (((uint8_t *) bitmap)[p >> 3] & (1u << (p & 7))) != 0 ) goto e1;
    p++;
  }

  while( p + 8 <= size && (p & (SIZEOF_INTMAX_T * 8 - 1)) != 0 ){
    if( ((uint8_t *) bitmap)[p >> 3] != 0 ) break;
    p += 8;
  }

  while( p + SIZEOF_INTMAX_T * 8 <= size ){
    if( *(uintmax_t *) ((uintptr_t) bitmap + (p >> 3)) != 0 ) break;
    p += SIZEOF_INTMAX_T * 8;
  }

#if SIZEOF_INTMAX_T > 4
  if( p + 4 * 8 <= size && *(uint32_t *) ((uintptr_t) bitmap + (p >> 3)) == 0 ) p += 4 * 8;
#endif

  if( p + 2 * 8 <= size && *(uint16_t *) ((uintptr_t) bitmap + (p >> 3)) == 0 ) p += 2 * 8;

  if( p + 8 <= size && ((uint8_t *) bitmap)[p >> 3] == 0 ) p += 8;

  while( p < size && (((uint8_t *) bitmap)[p >> 3] & (1u << (p & 7))) == 0 ) p++;

e1:
  *pos = p;
}
//-----------------------------------------------------------------------------
static __inline__ void lookup_zero_bit_range(
  const void * bitmap,uintptr_t size,uintptr_t * pos,uintptr_t * zero)
{
  uintptr_t p;

  lookup_zero_bit(bitmap,size,pos);
  p = *pos;
  lookup_non_zero_bit(bitmap,size,&p);
  *zero = p - *pos;
}
//-----------------------------------------------------------------------------
static __inline__ void lookup_max_zero_bit_range(
  const void * bitmap,
  uintptr_t size,
  uintptr_t * pos,
  uintptr_t * zero,
  uintptr_t * count)
{
  uintptr_t mpos = *pos, mzero;

  *zero = 0;

  while( mpos < size ){
    lookup_zero_bit_range(bitmap,size,&mpos,&mzero);

    if( mzero > *zero ){
      *zero = mzero;
      *pos = mpos;
    }

    *count += mzero;
    mpos += mzero;
  }
}
//-----------------------------------------------------------------------------
static __inline__ void lookup_min_zero_bit_range(
  const void * bitmap,
  uintptr_t size,
  uintptr_t * pos,
  uintptr_t * zero,
  uintptr_t * count)
{
  uintptr_t mpos = *pos, mzero;

  *zero = (uintptr_t) ~(uintptr_t) 0;

  while( mpos < size ){
    lookup_zero_bit_range(bitmap,size,&mpos,&mzero);

    if( mzero < *zero ){
      *zero = mzero;
      *pos = mpos;
    }

    *count += mzero;
    mpos += mzero;
  }
}
//-----------------------------------------------------------------------------
bool index_is_block_index_extent(struct index * idx,const byte_size_int * block_index)
{
  uint64_t bindex = bsint_get_be64toh(block_index,idx->block_index_size);
  uint64_t bextent = bindex / idx->cache->extent_size;
  return bindex == 2 || (bindex > 0 && bindex == bextent * idx->cache->extent_size);
}
//-----------------------------------------------------------------------------
void index_block_allocate(struct index * idx,byte_size_int * block_index)
{
  byte_size_int * bitmap_block_index = alloca(idx->block_index_size);
  uintptr_t pos;

  uint64_t extent = 0;

  struct index_link * link;

  for(;;){
    bsint_set_htobe64(bitmap_block_index,idx->block_index_size,
      extent == 0 ? 2 : extent * idx->cache->extent_size);

    link = index_link_block(idx,bitmap_block_index);
    rwlock_acquire_write_lock(&link->lock);

    pos = extent == 0 ? 3 : 1;
    lookup_zero_bit(link->blk,idx->cache->extent_size,&pos);

    if( pos < idx->cache->extent_size ){
      bsint_set_htobe64(block_index,idx->block_index_size,extent * idx->cache->extent_size + pos);

      //TODO:
      //rwlock_upgrade(&link->lock);

      if( get_bit(link->blk,pos) ){ // if other thread already alloc then retry lookup
        pos = extent == 0 ? 3 : 1;
        lookup_zero_bit(link->blk,idx->cache->extent_size,&pos);
      }

      if( pos < idx->cache->extent_size )
        set_bit(link->blk,pos);

      //rwlock_downgrade(&link->lock);
    }

    rwlock_release_write_lock(&link->lock);

    extent++;
    mutex_acquire(&idx->cache->links_mutex);
    link->linked--;
    mutex_release(&idx->cache->links_mutex);

    if( pos < idx->cache->extent_size ) break;
  }
}
//---------------------------------------------------------------------------
void index_block_release(struct index * idx,const byte_size_int * block_index)
{
  struct index_link * link;
  uint64_t block_index_v = bsint_get_be64toh(block_index,idx->block_index_size);
  uint64_t extent = block_index_v / idx->cache->extent_size;
  uint64_t extent_block_index = extent == 0 ? 2 : extent * idx->cache->extent_size;
  byte_size_int * bitmap_block_index = alloca(idx->block_index_size);
  
  bsint_set_htobe64(bitmap_block_index,idx->block_index_size,extent_block_index);

  link = index_link_block(idx,bitmap_block_index);
  rwlock_acquire_write_lock(&link->lock);
  reset_bit(link->blk,block_index_v & (idx->cache->extent_size - 1));
  rwlock_release_write_lock(&link->lock);

  mutex_acquire(&idx->cache->links_mutex);
  link->linked--;
  mutex_release(&idx->cache->links_mutex);
}
//---------------------------------------------------------------------------
